package class02;

import java.util.Arrays;

/*
 * 题目描述：
 * 有 N 个司机（N 为偶数），每个司机可以选择去 A 城市或 B 城市接送乘客。
 * 每个司机去不同城市可以获得不同的收入，给定一个 N*2 的矩阵表示每个司机去两个城市的收入。
 * 要求将司机平均分配到两个城市（每个城市 N/2 人），使得所有司机的总收入最大。
 * 
 * 示例：
 * 输入: [[10,20],[30,200],[400,50],[30,20]]
 * 输出: 470
 * 解释: 第一个和第二个司机去 A 城市，获得 10+30=40；第三个和第四个司机去 B 城市，获得 50+20=70；总收入 110
 * 但最优策略是第一个和第三个司机去 A 城市，获得 10+400=410；第二个和第四个司机去 B 城市，获得 200+20=220；总收入 630
 * 
 * 解题思路：
 * 1. 暴力递归方法：尝试所有分配方案，找出最大收入
 * 2. 动态规划方法：优化递归过程，避免重复计算
 * 3. 贪心策略：计算每个司机去两个城市的收入差值，根据差值进行排序分配
 */
public class Code04_Drive {

	// 课上的现场版本
	// income -> N * 2 的矩阵 N是偶数！
	// 0 [9, 13]
	// 1 [45,60]
	public static int maxMoney1(int[][] income) {
		if (income == null || income.length < 2 || (income.length & 1) != 0) {
			return 0;
		}
		int N = income.length; // 司机数量一定是偶数，所以才能平分，A N /2 B N/2
		int M = N >> 1; // M = N / 2 要去A区域的人
		return process1(income, 0, M);
	}

	// index.....所有的司机，往A和B区域分配！
	// A区域还有rest个名额!
	// 返回把index...司机，分配完，并且最终A和B区域同样多的情况下，index...这些司机，整体收入最大是多少！
	public static int process1(int[][] income, int index, int rest) {
		// 基础情况：所有司机都已经分配完毕
		if (index == income.length) {
			return 0;
		}
		// 还剩下司机！
		// 如果剩余司机数量等于A区域剩余名额，那么这些司机都必须去A区域
		if (income.length - index == rest) {
			return income[index][0] + process1(income, index + 1, rest - 1);
		}
		// 如果A区域没有名额了，那么剩余司机都必须去B区域
		if (rest == 0) {
			return income[index][1] + process1(income, index + 1, rest);
		}
		// 当前司机，可以去A，或者去B
		// 选择去A区域的收益 + 后续分配的最优收益
		int p1 = income[index][0] + process1(income, index + 1, rest - 1);
		// 选择去B区域的收益 + 后续分配的最优收益
		int p2 = income[index][1] + process1(income, index + 1, rest);
		// 返回两种选择中的最大收益
		return Math.max(p1, p2);
	}

	// 严格位置依赖的动态规划版本
	public static int maxMoney2(int[][] income) {
		int N = income.length;
		int M = N >> 1;
		// dp[i][j] 表示从第i个司机开始分配，A区域还有j个名额时的最大收入
		int[][] dp = new int[N + 1][M + 1];
		// 从后往前填表
		for (int i = N - 1; i >= 0; i--) {
			for (int j = 0; j <= M; j++) {
				// 如果剩余司机数量等于A区域剩余名额，这些司机都必须去A区域
				if (N - i == j) {
					dp[i][j] = income[i][0] + dp[i + 1][j - 1];
				// 如果A区域没有名额了，剩余司机都必须去B区域
				} else if (j == 0) {
					dp[i][j] = income[i][1] + dp[i + 1][j];
				} else {
					// 当前司机可以去A区域或B区域，选择收益更大的方案
					int p1 = income[i][0] + dp[i + 1][j - 1]; // 去A区域
					int p2 = income[i][1] + dp[i + 1][j];     // 去B区域
					dp[i][j] = Math.max(p1, p2);
				}
			}
		}
		return dp[0][M];
	}

	// 这题有贪心策略 :
	// 假设一共有10个司机，思路是先让所有司机去A，得到一个总收益
	// 然后看看哪5个司机改换门庭(去B)，可以获得最大的额外收益
	// 这道题有贪心策略，打了我的脸
	// 但是我课上提到的技巧请大家重视
	// 根据数据量猜解法可以省去大量的多余分析，节省时间
	// 这里感谢卢圣文同学
	public static int maxMoney3(int[][] income) {
		int N = income.length;
		// 记录每个司机去B城市比去A城市多获得的收益
		int[] arr = new int[N];
		// 先计算所有司机都去A城市的总收益
		int sum = 0;
		for (int i = 0; i < N; i++) {
			arr[i] = income[i][1] - income[i][0];
			sum += income[i][0];
		}
		// 按照收益差值排序，差值大的排在后面
		Arrays.sort(arr);
		int M = N >> 1;
		for (int i = N - 1; i >= M; i--) {
			sum += arr[i];
		}
		return sum;
	}

	// 找到了leetcode上的测试
	// leetcode上让求最小，课上讲的求最大
	// 其实是一个意思
	// 测试链接 : https://leetcode.cn/problems/two-city-scheduling/
	public static int twoCitySchedCost(int[][] costs) {
		int N = costs.length;
		// 记录每个司机去B城市比去A城市多花费的成本（可能是负数，表示节省的成本）
		int[] arr = new int[N];
		// 先计算所有司机都去A城市的总成本
		int sum = 0;
		for (int i = 0; i < N; i++) {
			arr[i] = costs[i][1] - costs[i][0];
			sum += costs[i][0];
		}
		// 按照成本差值排序
		Arrays.sort(arr);
		int M = N >> 1;
		for (int i = 0; i < M; i++) {
			sum += arr[i];
		}
		return sum;
	}

	// 返回随机len*2大小的正数矩阵
	// 值在0~value-1之间
	public static int[][] randomMatrix(int len, int value) {
		int[][] ans = new int[len << 1][2];
		for (int i = 0; i < ans.length; i++) {
			ans[i][0] = (int) (Math.random() * value);
			ans[i][1] = (int) (Math.random() * value);
		}
		return ans;
	}

	public static void main(String[] args) {
		int N = 10;
		int value = 100;
		int testTime = 500;
		System.out.println("测试开始");
		for (int i = 0; i < testTime; i++) {
			int len = (int) (Math.random() * N) + 1;
			int[][] matrix = randomMatrix(len, value);
			int ans1 = maxMoney1(matrix);
			int ans2 = maxMoney2(matrix);
			int ans3 = maxMoney3(matrix);
			if (ans1 != ans2 || ans1 != ans3) {
				System.out.println(ans1);
				System.out.println(ans2);
				System.out.println(ans3);
				System.out.println("Oops!");
			}
		}
		System.out.println("测试结束");
	}

}
